# 56/100 回溯-子集
# leetcode第46题: https://leetcode.cn/problems/subsets/description/?envType=study-plan-v2&envId=top-100-liked
# Date: 2024/12/2

from leetcode import test
from itertools import permutations


def subsets_bf(nums: list[int]) -> list[list[int]]:
    """一种错误的写法, 如nums = [1, 2, 3]时, 没有考虑[1,3]这样跳过中间元素的情况"""
    n = len(nums)
    if n < 2:
        return [[], nums]

    res = [[]]
    for start in range(n):
        for length in range(1, n - start + 1):
            res.append(nums[start:start + length])

    return res


def subsets_backtracking(nums: list[int]) -> list[list[int]]:
    """使用回溯法"""
    if len(nums) < 2:
        return [[], nums]

    def backtracking(index, path):
        res.append(path[:])
        for i in range(index, len(nums)):
            path.append(nums[i])
            backtracking(i + 1, path)
            path.pop()

    res = []
    backtracking(0, [])

    return sorted(res)


if __name__ == '__main__':
    inp = [{"nums": [1, 2, 3]}, {"nums": [0]}, ]

    out = [sorted([[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]),
           sorted([[], [0]])]

    test.test_function(subsets_bf, inp, out)
    test.test_function(subsets_backtracking, inp, out)
